#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>

void bubble_sort(std::vector<int>& nums)
{
	// 冒泡排序，依次比较，将最大的元素放到最后一个位置，然后对前n-1个重复该操作
	// 优化：如果在一趟排序过程中，没有发生任何交换，说明已经有序，直接返回
	int n = nums.size();
	for (int i = 0; i < n; i++) {
		int flag = 0;
		for (int j = 1; j < n - i; j++) {
			if (nums[j - 1] > nums[j]) {
				std::swap(nums[j - 1], nums[j]);
				flag = 1;
			}
		}
		if (!flag) break; // 如果本次循环没有发生任何交换，说明数组已经有序，直接退出
	}
}

void insert_sort(std::vector<int>& nums)
{
	// 插入排序，将数组分为有序和无序两部分
	// 依次拿出无序的第一个元素，与有序部分进行比较，如果大于，则就插入在该位置
	// 如果小于，则将有序部分向后挪，继续根前一个比较

	int n = nums.size();
	for (int i = 0; i < n - 1; i++) {
		int end = i; // 有序部分的最后一个元素
		int tmp = nums[end + 1];

		while (end >= 0) {
			if (nums[end] <= tmp) break;
			nums[end + 1] = nums[end];
			end--;
		}
		nums[end + 1] = tmp;
	}
}

void shell_sort(std::vector<int>& nums)
{
	// 希尔排序
	int n = nums.size();
	int gap = n;
	while (gap > 1) {
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; i += gap) {
			int end = i;
			int tmp = nums[end + gap];

			while (end >= 0) {
				if (nums[end] <= tmp) break;
				nums[end + gap] = nums[end];
				end -= gap;
			}
			nums[end + gap] = tmp;
		}
	}
}

void select_sort(std::vector<int>& nums)
{
	// 选择排序
	// 遍历数组，依次选择最小的元素放在头部
	int n = nums.size();
	for (int i = 0; i < n; i++) {
		int minIndex = i;
		for (int j = i + 1; j < n; j++) {
			minIndex = nums[minIndex] < nums[j] ? minIndex: j;
		}
		std::swap(nums[minIndex], nums[i]);
	}
}

// 向下调整
// 升序，建大堆
void adjust_down(std::vector<int>& nums, int parent, int size)
{
	int child = parent * 2 + 1;
	int val = nums[parent];
	while (child < size) {
		// 假设法，求出最大的孩子
		if (child + 1 < size && nums[child + 1] > nums[child]) {
			child += 1;
		}

		if (val >= nums[child]) break;
		nums[parent] = nums[child];
		parent = child;
		child = parent * 2 + 1;
	}

	nums[parent] = val;
}

void heap_sort(std::vector<int>& nums)
{
	// 堆排序
	// 先从倒数第一个非叶子节点开始向下调整
	int n = nums.size();
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		adjust_down(nums, i, n);
	}

	// 交换堆顶元素和相对的最后一个元素，交换完成后进行向下调整
	int end = n - 1;
	while (end >= 0) {
		std::swap(nums[0], nums[end]);
		adjust_down(nums, 0, end);
		end--;
	}
}

void hoare_sort(std::vector<int>& nums, int left, int right)
{
	if (left >= right) return;

	int pivot = nums[left];
	int L = left; // 从左往右，找大
	int R = right; // 从右往左，找小
	while (L < R) {
		// 先找小	
		while (R > L && nums[R] >= pivot) R--;

		// 再找大
		while (R > L && nums[L] <= pivot) L++;

		std::swap(nums[R], nums[L]);
	}
	std::swap(nums[L], nums[left]);

	// 此时区间被分为 [left L-1] L [L + 1, right]
	// 分别对左右区间使用霍尔快排
	hoare_sort(nums, left, L - 1);
	hoare_sort(nums, L + 1, right);
}

// 三路划分
std::pair<int, int> partition(std::vector<int>& nums, int left, int right)
{
	int pivot = nums[left];
	int lt = left;
	int rt = right;

	// [left, lt) [lt, rt] (rt, right]
	int i = left + 1;
	while (i <= rt) {
		if (nums[i] < pivot) std::swap(nums[i++], nums[lt++]);
		else if (nums[i] > pivot) std::swap(nums[i], nums[rt--]);
		else i++;
	}

	return { lt, rt };
}

void quick_sort(std::vector<int>& nums, int left, int right)
{
	if (left >= right) return;
	std::pair<int, int> range = partition(nums, left, right);

	quick_sort(nums, left, range.first - 1);
	quick_sort(nums, range.second + 1, right);
}

// 归并排序
void _merge_sort(std::vector<int>& nums, std::vector<int>& tmp, int left, int right)
{
	if (left >= right) return;

	// 1.将区间分为两部分，分别进行归并排序
	int mid = (right - left) / 2 + left;
	// [left, mid] [mid + 1, right]
	_merge_sort(nums, tmp, left, mid);
	_merge_sort(nums, tmp, mid + 1, right);

	// 2.合并两个有序数组
	int i = left, j = mid + 1;
	int k = left;
	while (i <= mid && j <= right) {
		if (nums[i] > nums[j]) tmp[k++] = nums[j++];
		else tmp[k++] = nums[i++];
	}

	// 3.判断那个区间还有剩余
	while (i <= mid) tmp[k++] = nums[i++];
	while (j <= right) tmp[k++] = nums[j++];

	// 4.将辅助数组的内容拷贝会原空间
	memcpy(&nums[left], &tmp[left], sizeof(int)*(right - left + 1));
}

void merge_sort(std::vector<int>& nums)
{
	std::vector<int> tmp;
	tmp.resize(nums.size());

	_merge_sort(nums, tmp, 0, nums.size() - 1);
}

int main()
{
	//std::vector<int> nums({ 10,9,8,7,6,5,4,3,2,1});
	std::vector<int> nums({ 1,2,10,8,7,6,5,4,});
	for (const int& e : nums) std::cout << e << " ";
	std::cout << std::endl;

	//bubble_sort(nums);
	//insert_sort(nums);
	//shell_sort(nums);
	//select_sort(nums);
	//heap_sort(nums);
	//hoare_sort(nums, 0, nums.size() - 1);
	//quick_sort(nums, 0, nums.size() - 1);
	merge_sort(nums);

	for (const int& e : nums) std::cout << e << " ";
	std::cout << std::endl;
	return 0;
}